1. Field of the Invention
This invention relates to the field of computer software optimization. More particularly, the present invention relates to a method for eliminating common subexpressions in computer code.
2. History of the Prior Art
Computer programs are generally created as source code. The source code is compiled into object code for execution on a specific processor. Hence, most programs exist as compiled object code in computer systems. The compiled object code is usually designed/compiled to operate on only one particular operating system and/or on only one particular computer processor architecture. In order to use a certain program on several different computer systems, the original source code must be compiled into object code for each different operating system and each different processor architecture.
The popularization of the World Wide Web has exacerbated a problem for software developers trying to create software for networked consumer devices. While millions of people around the globe are surfing the Internet and browsing web pages with their computers, not all of those computers are the same. One person may be using a Macintosh, another a PC, and yet another user with a UNIX machine. Hence computer programs need to be designed to support multiple host architectures and to allow secure delivery of its software components. As a result, Sun Microsystems Inc., developed Java. Java is a general purpose, concurrent object oriented programming language that supports a highly portable programming environment. Java was designed such that its code could survive transport access networks and operate on any client, while assuring the client that the program was safe to run.
A Java program is created by compiling source code written in Java's well defined source code format into a compact, architecture-neural object code known as Java bytecodes. Compilation normally consisting of translating Java source code into a machine independent bytecode representation. Bytecodes are executed at runtime by an interpreter residing on the client computer. Runtime activities may include loading and linking the classes needed to execute a program, native machine code generation and dynamic optimization of the program, and actual program execution.
Java bytecodes are designed to operate on a Java Virtual Machine (VM). The Java Virtual Machine is an abstract computing machine that has its own instruction set and uses various memory areas. A Java VM is not an actual hardware platform, but rather a low level software emulator that can be implemented on many different processor architectures and under many different operating systems. The Java VM reads and interprets each bytecode so that the instructions may be executed by the native microprocessor. Hence compiled Java bytecodes are capable of functioning on any platform that has a Java Virtual Machine implementation available. However, bytecode interpretation detracts from processor performance since the microprocessor has to spend part of its processing time interpreting bytecodes. Java "Just-In-Time" (JIT) compilers were introduced to improve the performance of Java Virtual Machines. A Java JIT compiler translates Java bytecodes into the processor's native machine code during runtime. The processor then executes the compiled native processor object code like any other native program. Such compiled Java programs execute much faster than Java programs that are executed using a Java interpreter.
Although a Just-In-Time compiled Java program executes faster than an interpreted Java program, the performance of such Just-In-Time compiled Java programs can be further improved. Since Just-In-Time compilations must be performed very quickly to provide an immediate response to the user, Just-In-Time compiled code is usually not very well optimized. The importance of compilation speed in a Java JIT compiler creates the additional requirement that optimization algorithms be lightweight and effective.